package LimitedTimeGame.Day_0213;

/**
 * @author zxc
 * @date 2023/02/13 16:48
 **/

import java.util.HashMap;

/**
 * 题目 ：替换子串得到平衡字符串
 * 题目详述 ：
 * 有一个只含有'Q', 'W', 'E','R'四种字符，且长度为 n的字符串。
 * 假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 * 你可以用和「待替换子串」长度相同的任何 其他字符串来完成替换。
 * 请返回待替换子串的最小可能长度。
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 *
 * 提示：
 * 1 <= s.length <= 10^5
 * s.length 是 4 的倍数
 * s 中只含有 'Q', 'W', 'E', 'R' 四种字符
 *
 */
public class BalancedString {
    public static void main(String[] args) {
        System.out.println(balancedString("QQWE"));
    }
    /**
     * 思路 ：
     * （1）平衡字符串定义为 ：长度为4 * n的字符串str && 字符串str由'Q','W','E','R'等四个字符组成
     *  ===》 即，代表了每个字符的数量都是 n ;
     *  思路 ：
     * （1）由于所要截取的子字符串是连续的，所以比较适合使用滑动窗口机制，来获取所有可能的子字符串;
     * （2）要判断是否能够所截取的子字符串进行修改之后，能够组成平衡字符串
     * ===》 即，通过判断主字符串s删除子字符串str之后，是否能够满足每一个字符 都小于或等于len（len == s.length()）
     * （3）滑动窗口 ： 即，左指针指向滑动窗口的最左元素，右指针指向滑动窗口的最右元素;
     * ===>
     * 核心思想 ：即，当右指针找到适合条件的子字符串时，只需要移动左指针去寻找符合条件的最小子字符串即可;
     * 结束条件 ：当滑动窗口机制的右指针遍历到主字符串s的最后一个字符;
     *
     * @param s
     * @return
     */
    public static int balancedString(String s) {
        int len = s.length();
        HashMap<Character , Integer> hashMap = new HashMap<>();
        // 需要保证这四个字符多对应的键值对是必须存在的 && 同时保证其初始化的值为0;
        hashMap.put('Q' , 0);
        hashMap.put('W' , 0);
        hashMap.put('E' , 0);
        hashMap.put('R' , 0);
        // 每次遍历都需要将哈希表进行恢复;
        for (char ch : s.toCharArray()) {
            hashMap.put(ch , hashMap.get(ch) + 1);
        }
        if(isLowerLen(hashMap , len / 4)){
            return 0;
        }
        int p1 = 0;
        int p2 = 0;
        int min = Integer.MAX_VALUE;
        while(p2 <= len){
            if (isLowerLen(hashMap, len / 4)) {
                while(p1 < p2 && isLowerLen(hashMap , len / 4)){
                    hashMap.put(s.charAt(p1) , hashMap.get(s.charAt(p1)) + 1);
                    p1++;
                }
                min = Math.min(min , p2 - p1 + 1);
            }
            if(p2 < len){
                Character ch = s.charAt(p2);
                hashMap.put(ch , hashMap.get(ch) - 1);
            }
            p2++;
        }
        return min;
    }

    private static boolean isLowerLen(HashMap<Character, Integer> hashMap , Integer len) {
        if(hashMap.get('Q') <= len && hashMap.get('W') <= len && hashMap.get('E') <= len && hashMap.get('R') <= len){
            return true;
        }
        return false;
    }
}
